/*
https://leetcode-cn.com/problems/bricks-falling-when-hit/solution/803-da-zhuan-kuai-by-leetcode-r5kf/
 */
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution803 {

    int[] dx={1,0,-1,0};
    int[] dy={0,1,0,-1};

    public int[] hitBricks(int[][] grid, int[][] hits) {
        int m=grid.length,n=grid[0].length;
        int[][] copy=new int[m][n];
        for (int i=0;i<m;i++){
            copy[i]=Arrays.copyOf(grid[i],n);
        }
        for (int[] hit : hits) {
            copy[hit[0]][hit[1]]=0;
        }
        int[] b=new int[m*n+1];
        int[] size=new int[m*n+1];
        for (int i=0;i<m*n+1;i++){
            b[i]=i;
            size[i]=1;
        }
        for (int i=0;i<n;i++){
            if (copy[0][i]==1){
                int x=find(b,i);
                int y=find(b,m*n);
                if (x!=y){
                    b[x]=y;
                    size[y]+=size[x];
                }
            }
        }
        for (int i=1;i<m;i++){
            for (int j=0;j<n;j++){
                if (copy[i][j]==1) {
                    if (copy[i-1][j]==1){
                        int x=find(b,i*n+j);
                        int y=find(b,(i-1)*n+j);
                        if (x!=y){
                            b[x]=y;
                            size[y]+=size[x];
                        }
                    }
                    if (j>0 && copy[i][j-1]==1) {
                        int x=find(b,i*n+j);
                        int y=find(b,i*n+j-1);
                        if (x!=y) {
                            b[x]=y;
                            size[y]+=size[x];
                        }
                    }
                }
            }
        }
        int[] res=new int[hits.length];
        for (int i=hits.length-1;i>=0;i--) {
            int[] hit=hits[i];
            if (grid[hit[0]][hit[1]]==0){
                continue;
            }
            int s1=size[find(b,m*n)];
            if (hit[0]==0){
                int xx=find(b, hit[1]);
                int yy=find(b,m*n);
                if (xx!=yy){
                    b[xx]=yy;
                    size[yy]+=size[xx];
                }
            }
            for (int j=0;j<4;j++){
                int x=hit[0]+dx[j];
                int y=hit[1]+dy[j];
                if (valid(x,y,m,n) && copy[x][y]==1){
                    int xx=find(b,hit[0]*n+hit[1]);
                    int yy=find(b,x*n+y);
                    if (xx!=yy){
                        b[xx]=yy;
                        size[yy]+=size[xx];
                    }
                }
            }
            int s2=size[find(b,m*n)];
            res[i]=Math.max(s2-s1-1,0);
            copy[hit[0]][hit[1]]=1;
        }
        return res;
    }

    boolean valid(int x,int y,int m,int n){
        return x>=0 && x<m && y>=0 && y<n;
    }

    int find(int[] b,int k){
        List<Integer> list=new ArrayList<>();
        while (k!=b[k]){
            list.add(k);
            k=b[k];
        }
        for (Integer integer : list) {
            b[integer]=k;
        }
        return k;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution803().hitBricks(new int[][]{{1,0,0,0},{1,1,1,0}},new int[][]{{1,0}})));
    }
}
